/**
 * @file 狄杰斯特拉算法
 * @author
 */
const matrix= [
    [0, 7, 2, Infinity, 6, 9],
    [6, 0, 3, Infinity, Infinity, 8],
    [2, 4, 0, 5, Infinity, 7],
    [Infinity, Infinity, 8, 0, 1, Infinity],
    [9, Infinity, Infinity, 1, 0, Infinity]
    [8, 6, Infinity, 9, 7, 0]
];

// 经典狄杰斯特拉
const dijkstra = (matrix) => {
    const pointCount = matrix.length;
    // 每一个点，到原点的距离集合
    const disMap = Array(pointCount).fill(Infinity);

    // 从0点作为起始
    disMap[0] = 0;

    for (let i = 0; i < pointCount; i++) {
        // 不可达
        if (disMap[i] >= Infinity) {
            continue;
        }
        for (let j = 0; j < pointCount; j++) {
            // 从i到j的距离 加上 i的已知距离，小于到j目前的已知距离
            // 则更新
            if (disMap[i] + matrix[i][j] < disMap[j]) {
                disMap[j] = disMap[i] + matrix[i][j];
            }
        }
    }
    return disMap;
};

const start = () => {
    const minDis = dijkstra(matrix);
    const endPoint = 3;
    console.log('minDis::', minDis);
};

start();
